这道题一看就是到好(shui)题,毕竟自己因long long的问题的错了几次。好吧,不废话,开始讲解:
这道题一看就是求无向图中,去掉一个点后无法连通的点对,但注意:
首先 跟其他个点肯定不能互通。如果是割点,那么去掉之后的几个不同连通分量就不能互通,那我们现在就想办法求一下去掉后被切断的连通分量。先观察一下下图:

黄点是一个割点,我们先考虑以它为根的子树的联通情况:
我们用表示以为根的子树的大小,显然
这个我们可以在中算出。
我们再定义为当前u已经遍历到的子树的节点个数,为去掉点后子树中的点无法连通的情况。
那么,每次遍历子节点 , ,
现在在考虑子树内部与外部的联通情况,的子树大小为,外部节点为,去掉点后,这些点也是无法连通的,为去掉u点后子树中的点与外部的点无法连通的情况。
那么,
结合注意事项1,2,我们可以得到:,这就是最后的答案了。
代码如下:
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 100000;
int n,m,x,y;
vector< int > Graph[ MAXN + 5 ];
void Read( int &x ) {
int f = 1;
x = 0;
char s = getchar( );
while( s < '0' || s > '9' ) {
if( s == '-' ) f = -1;
s = getchar( );
}
while( s >= '0' && s <= '9' ) {
x = x * 10 + s - 48;
s = getchar( );
}
x *= f;
}
void Write( long long x ) {
if( x < 0 ) {
x = -x;
putchar('-');
}
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + 48 );
}
int Max( int x , int y ) {
return x > y ? x : y;
}
int Min( int x , int y ) {
return x < y ? x : y;
}
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , child[ MAXN + 5 ] , depth;
long long Ans[ MAXN + 5 ];
void Tarjan( int u , int fa ) {
dfn[ u ] = low[ u ] = ++ depth;
child[ u ] = 1;
//printf("%d %d\n",u,depth);
long long sum = 0;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
if( !dfn[ v ] ) {
Tarjan( v , u );
child[ u ] += child[ v ];
if( low[ v ] >= dfn[ u ] ) {
Ans[ u ] += child[ v ] * sum;
sum += child[ v ];
}
low[ u ] = Min( low[ u ] , low[ v ] );
}
else if( v != fa && dfn[ u ] > dfn[ v ] )
low[ u ] = Min( low[ u ] , dfn[ v ] );
}
Ans[ u ] = ( Ans[ u ] + sum * ( n - sum - 1 ) + n - 1 ) * 2;
}
int main( ) {
Read( n ) , Read( m );
for( int i = 1 ; i <= m ; i ++ ) {
Read( x ) , Read( y );
Graph[ x ].push_back( y );
Graph[ y ].push_back( x );
}
Tarjan( 1 , -1 );
for( int i = 1 ; i <= n ; i ++ )
Write( Ans[ i ] ) , putchar('\n');
return 0;
}